#include <stdio.h>                                                                      
#include <stdlib.h>                                                                     
#define DataType char                                                                   
#define MAXLENGTH 400                                                                    
//Define Sequence Stack (Char)//
                                                                                        
struct SeqStack{                                                                        
       int MAXNUM;                                                                      
       int t;                                                                           
       DataType *s;                                                                     
};                                                                               
typedef struct SeqStack *PSeqStack;                                                     
                                                                                        
//Define Creating a Sequence Stack       
PSeqStack createEmptyStack_seq(int m){                                                  
    PSeqStack pastack=(PSeqStack)malloc(sizeof(struct SeqStack));                 
    if (pastack!=NULL){                                                           
        pastack->s=(DataType *)malloc(sizeof(DataType) *m);                       
        if (pastack->s){                                            
                       pastack->MAXNUM=m;                           
                       pastack->t=-1;                               
                       return pastack;                              
        }                                            
        else free (pastack);                                        
    }                                                           
    printf("Out of space!!\n");                                                   
    return NULL;                                                                  
}                                                                             
//Define Checking whether a Sequence Stack is empty 
int isEmptyStack_seq(PSeqStack pastack){                                                
    int stack_top=pastack->t;                                                           
    if (stack_top==-1){                                                                 
       return 1;                                                          
    }                                                                  
    else return 0;                                                                      
}                                                                                   
//Define Pushing an element ("x") into a Sequence Stack ("pastack")       
void push_seq(PSeqStack pastack, DataType x){                                           
     if (pastack->t>=pastack->MAXNUM-1)                                                 
        printf("Overflow, pushing failed!\n");                                          
     else {                                                                              
          pastack->t=pastack->t+1;                                                      
          pastack->s[pastack->t]=x;                                                     
     }                                                                             
}                                                                                  
//Define Poping an element out from a Sequence Stack ("pastack")     
void pop_seq(PSeqStack pastack){                                                        
     if (pastack->t<0)                                                                  
        printf("Underflow, poping failed!\n");                                          
     else {                                                                              
          pastack->t=pastack->t-1;                                                      
     }                                                                             
}                                                                                  
//Define getting Top element out from a Sequence Stack ("pastack")   
DataType top_seq(PSeqStack pastack){                                                    
     if (pastack->t<0)                                                                  
        printf("This stack is empty!\n");                                               
     else {                                                                              
          return pastack->s[pastack->t];                                                
     }                                                                             
}                                                                                  
                                                                                        
                                                                                        
                                                                                        
//Define Sequence Stack (Int)                                                                   
struct DSeqStack{                                                                       
       int MAXNUM;                                                                      
       int t;                                                                           
       int *s;                                                                          
};                                                                               
typedef struct DSeqStack *PDSeqStack;                                                                                                                                   
//Define Creating a DSequence Stack     
PDSeqStack createEmptyStack_dseq(int m){                                                
    PDSeqStack pastack=(PDSeqStack)malloc(sizeof(struct DSeqStack));              
    if (pastack!=NULL){                                                           
       pastack->s=(int *)malloc(sizeof(int) *m);                   
       if (pastack->s){                                            
       pastack->MAXNUM=m;                           
       pastack->t=-1;                               
       return pastack;                              
       }                                            
       else free (pastack);                                        
       }                                                           
    printf("Out of space!!\n");                                                   
    return NULL;                                                                  
}                                                                             
//Define Checking whether a DSequence Stack is empty      
int isEmptyStack_dseq(PDSeqStack pastack){                                              
    int stack_top=pastack->t;                                                           
    if (stack_top==-1){                                                                 
                     return 1;                                                          
                     }                                                                  
    else return 0;                                                                      
}                                                                                   
//Define Pushing an element ("x") into a DSequence Stack ("pastack")/      
void push_dseq(PDSeqStack pastack, int x){                                              
     if (pastack->t>=pastack->MAXNUM-1)                                                 
        printf("Overflow, pushing failed!\n");                                          
     else {                                                                              
          pastack->t=pastack->t+1;                                                      
          pastack->s[pastack->t]=x;                                                     
          }                                                                             
}                                                                                  
//Define Poping an element out from a DSequence Stack ("pastack")    
void pop_dseq(PDSeqStack pastack){                                                      
     if (pastack->t<0)                                                                  
        printf("Underflow, poping failed!\n");                                          
     else {                                                                              
          pastack->t=pastack->t-1;                                                      
          }                                                                             
}                                                                                  
//Define getting Top element out from a DSequence Stack ("pastack")    
int top_dseq(PDSeqStack pastack){                                                       
     if (pastack->t<0)                                                                  
        printf("This stack is empty!\n");                                               
     else {                                                                              
          return pastack->s[pastack->t];                                                
     }                                                                             
}                                                                                  
                                                                                        
                                                                                        
                                                                                        
//A Infix to RPolish Expression Converter   
int convertInfixRPolish (char *infix, char *rpolish){                                     
    PSeqStack ps_operator=createEmptyStack_seq(MAXLENGTH);                              
    int continuity=0,blanck_flag=0;                                                     
    char temp, temp_top=0;                                                              
    int i,j = 0;                                                                        
//LOOP STARTS!              
    for(i=0;infix[i]!=';';i++){                                                         
       temp=infix[i];                                                                
//Condition: Blanck      
       if (temp==' '){                                                               
         if (continuity==1){                                                         
             blanck_flag=1;                                                          
         }                                                                       
       }                                                                             
//Condition: Digit         
       else if (temp>='0'&&temp<='9'){                                               
        rpolish[j]=temp;                                                             
        j=j+1;                                                                      
        continuity=1;                                                               
        if (blanck_flag==1) return 0;                                               
       }                                                                             
//Condition: "+", "-"      
       else if (temp=='+'||temp=='-'){                                               
            blanck_flag=0;                                                           
        if(continuity==1){                                                          
         rpolish[j]=' ';                                                            
         j=j+1;                                                                    
          continuity=0;                                                             
         }                                                                           
         if (isEmptyStack_seq(ps_operator)==0){                                      
          temp_top=top_seq(ps_operator);                                            
          if (temp_top!='('&&temp_top!=')'){                                        
            rpolish[j]=temp_top;                                                     
             j=j+1;                                                              
             rpolish[j]=' ';                                                      
             j=j+1;                                                              
            pop_seq(ps_operator);                                                   
          }                                                                       
         }                                                                           
         push_seq(ps_operator,temp);                                                 
         temp_top=top_seq(ps_operator);                                              
       }                                                                             
//Condition: "*", "/"        
       else if (temp=='*'||temp=='/'){                                               
            blanck_flag=0;                                                           
        if (continuity==1){                                                          
          rpolish[j]=' ';                                                            
          j=j+1;                                                                    
           continuity=0;                                                             
            }                                                                           
         if (isEmptyStack_seq(ps_operator)==0){                                      
           temp_top=top_seq(ps_operator);                                            
           if (temp_top!='('&&temp_top!=')'&&temp_top!='+'&&temp_top!='-'){          
             rpolish[j]=temp_top;                                                     
              j=j+1;                                                                  
             pop_seq(ps_operator);                                                   
           }                                                                       
         }                                                                           
         push_seq(ps_operator,temp);                                                 
       }                                                                              
//Condition: "("        
       else if (temp=='('){                                                          
            blanck_flag=0;                                                           
          if(continuity==1){                                                          
           return 0;                                                                 
           break;                                                                    
           }                                                                           
         push_seq(ps_operator,temp);                                                 
       }                                                                              
//Condition: ")"        
       else if (temp==')'){                                                          
            blanck_flag=0;                                                           
        if(continuity==1){                                                          
         rpolish[j]=' ';                                                            
         j=j+1;                                                                    
          continuity=0;                                                             
         }                                                                           
        temp_top=top_seq(ps_operator);                                              
         while(isEmptyStack_seq(ps_operator)==0&&temp_top!='('){                     
          rpolish[j]=top_seq(ps_operator);                                           
          j=j+1;                                                                    
          pop_seq(ps_operator);                                                     
          temp_top=top_seq(ps_operator);                                            
          rpolish[j]=' ';                                                            
          j=j+1;                                                                    
          }                                                                         
         if (temp_top=='(') pop_seq(ps_operator);                                    
         else {                                                                      
              rpolish[0]='b';                                                            
              return 0;                                                                 
              break;                                                                    
              }                                                                          
       }                                                                              
//Other Conditions       
        else {                                                                          
         free(ps_operator);                                                            
         return 0;                                                                     
         }                                                                              
    }                                                                                   
//Breaks the Loop        
   if(continuity==1){                                                                   
     rpolish[j]=' ';                                                            
     j=j+1;                                                                    
     continuity=0;                                                             
   }                                                                           
   temp_top=top_seq(ps_operator);                                                       
    while(isEmptyStack_seq(ps_operator)==0&&temp_top!='('){                             
         temp_top=top_seq(ps_operator);                                            
         rpolish[j]=temp_top;                                                       
         j=j+1;                                                                    
         rpolish[j]=' ';                                                            
         j=j+1;                                                                    
         pop_seq(ps_operator);                                                     
    }                                                                         
    free(ps_operator);                                                                  
    rpolish[j]='\0';                                                                     
    if (temp_top=='('){                                                                 
       rpolish[0]='b';                                                            
       return 0;                                                                 
    }                                                                                   
    else return 1;                                                                      
    }                                                                                   
                                                                                        
                                                                                        
//A RPolish Expression Calculator              
int calculateRPolish(char *rpolish, int *result){                                         
                                                                                       
  int continuity=0;                                                                   
  PDSeqStack ps_digits=createEmptyStack_dseq(MAXLENGTH);                              
  int i;                                                                              
  char temp,dtemp;                                                                    
                                                                                      
  for(i=0;rpolish[i]!='\0';i++){                                                       
   temp=rpolish[i];                                                                   
//Condition: Digit-//           
      if (temp>='0'&&temp<='9'){                                                    
       if(continuity==1){                                                          
       dtemp=dtemp*10+temp-'0';                                                    
      }                                                                             
       else {                                                                      
       dtemp=temp-'0';                                                             
       }                                                                           
       continuity=1;                                                               
      }                                                                             
//Condition: Blank          
    else if (temp==' '){                                                             
       if(continuity==1){                                                          
        push_dseq(ps_digits,dtemp);                                               
        continuity=0;                                                             
        }                                                                         
      }                                                                            
//Condition: Operator      
      else if (temp=='+'||temp=='-'||temp=='*'||temp=='/'){                         
    if(continuity==1){                                                          
     push_dseq(ps_digits,dtemp);                                               
     continuity=0;                                                             
     }                                                                         
    if(isEmptyStack_dseq(ps_digits)){                                           
     return 0;                                                                 
     break;                                                                    
     }                                                                         
    int temp_1=top_dseq(ps_digits);                                             
    pop_dseq(ps_digits);                                                        
    if(isEmptyStack_dseq(ps_digits)){                                           
     return 0;                                                                 
     break;                                                                    
     }                                                                         
    int temp_2=top_dseq(ps_digits);                                             
    pop_dseq(ps_digits);                                                        
                                                                                
    int temp_3 = 0;                                                             
    switch(temp){                                                               
     case'+': temp_3=temp_2+temp_1; break;                                     
     case'-': temp_3=temp_2-temp_1; break;                                     
     case'*': temp_3=temp_2*temp_1; break;                                     
     case'/': temp_3=temp_2/temp_1; break;                                     
     default: return 0; break;                                                 
     }                                                                         
    push_dseq(ps_digits,temp_3);                                                
    }                                                                           
//Condition: Others       
      else {                                                                        
        free (ps_digits);                                                        
        return 0;                                                                
      }                                                                        
  }                                                                                 
  *result=top_dseq(ps_digits);                                                        
  pop_dseq(ps_digits);                                                                
   if(!isEmptyStack_dseq(ps_digits)){                                                  
   return 0;                                                                 
  }                                                                         
  return 1;                                                                           
   free(ps_digits);                                                                    
 }                                                                                     
                                                                                        
                                                                                        
int main(void)                                                                          
{                                                                                       
FILE *fr;                                                                               
fr=fopen("infix.dat","rt");                                                             
int i=0;                                                                                
int *result;                                                                            
char temp=0;                                                                            
char infix[100];                                                                        
char *rpolish;                                                                           
for(i=0;infix[i]!=EOF;i++){                                                             
   infix[i]=fgetc(fr);                                                               
   }                                                                                 
convertInfixRPolish (infix, rpolish);                                                     
if(convertInfixRPolish (infix, rpolish)==1){                                              
for(i=0;rpolish[i]!='\0';i++){                                                           
   printf("%c",rpolish[i]);                                                           
   }                                                                                 
}                                                                                       
else printf("Please check the infix!");                                                 
                                                                                        
if(calculateRPolish(rpolish,result)){                                                     
 printf("\nThe result is %d\n",*result);                                               
 }                                                                                     
else printf("RPolish Expression Error!");                                                
                                                                                       
fclose(fr);                                                                             
  system("PAUSE");                                                                     
  return 0;                                                                             
}                                                                                       
